// FRAOZO -Project 5b
// This file contains everything except the graph class

#include <iostream>
#include <limits.h>
#include "d_except.h"
#include <fstream>
#include "d_matrix.h"
#include "graph.h"
#include <stack>
#include <queue>

using namespace std;


struct nodeAndDir 
//Used to store the nodeId's and directions
//(go up/down/etc.) from start node to end node
{
      int nodeId;
      string direction;
};

class maze
{
   public:
      maze(ifstream &fin);

      int numRows(){return rows;};
      int numCols(){return cols;};

      void print(int,int,int,int);

      bool isLegal(int i, int j);
      bool isAdjacent(int row1, int col1, 
                      int row2, int col2);

      void setMap(int i, int j, int n);
      int getMap(int i, int j);
      void setReverseMap(int row, int col);
      int getReverseMapI(int n) const;
      int getReverseMapJ(int n) const;

      void mapMazeToGraph();

      void findPaths();
      string getDirection(int nodeSource, int nodeDest);
      

   private:
      //Members for mapping maze to graph
      void createNodes();
      void createEdges();
      void makeNewNode(int row, int col);
      void makeNewEdge(int, int, int, int);

      //Members for finding paths
      void findShortestPath1();
      void dfsRecursive(int currentNodeId,
                        stack<nodeAndDir> &currentPath);

      void findShortestPath2();
      stack<nodeAndDir> bfs();

      vector<int> getValidNeighbors(int currentNodeId);

      stack<nodeAndDir> reverseStack(stack<nodeAndDir> s);
      void printPath(stack<nodeAndDir> path);

      stack<nodeAndDir> traceMap(vector<int> map);

      int rows; // number of rows in the maze
      int cols; // number of columns in the maze
      
      int currentRow; //Row of the current position
      int currentCol; //Column of the current position
      int goalRow; 
      int goalCol;

      matrix<bool> value;
      matrix<int> cellToNode; //Matrix that maps i/j vals to nodeId
      vector< vector<int> > nodeToCell; //Vector of 2-element vectors
      
      graph mazeGraph; 
      stack<nodeAndDir> shortestPath; // Stores how to get to the goal

};

void maze::setMap(int i, int j, int n)
// Set mapping from maze cell (i,j) to graph node n. 
{
   cellToNode[i][j] = n;
}

int maze ::getMap(int i, int j)
// Return mapping of maze cell (i,j) in the graph.
{ 
   try 
   {
      isLegal(i, j);
   }
   catch (rangeError ex)
   {
      return -1;
   }
   
   if (!isLegal(i, j))
      return -1;
   
   return cellToNode[i][j];
}

void maze::setReverseMap(int row, int col)
//Push a vector containing row and col into nodeToCell
// Since the 2-element vector is always pushed into 
// nodeToCell, we can assume that the indeces of nodeToCell
// are the nodeId's (see getReverseMapI/J)
{
   vector<int> rowColVect;
   rowColVect.push_back(row);
   rowColVect.push_back(col);
   nodeToCell.push_back(rowColVect);
}

int maze ::getReverseMapI(int n) const
// Return reverse mapping of node n to it's maze i value.
{
   return nodeToCell[n][0];
}

int maze ::getReverseMapJ(int n) const
// Return reverse mapping of node n to it's maze j value.
{
   return nodeToCell[n][1];
}

maze::maze(ifstream &fin)
   :cellToNode(), nodeToCell(), mazeGraph()
    // Initializes a maze by reading values from fin.  Assumes that the
    // number of rows and columns indicated in the file are correct.
{
   fin >> rows;
   fin >> cols;

   char x;

   value.resize(rows,cols);
   for (int i = 0; i <= rows-1; i++)
      for (int j = 0; j <= cols-1; j++)
      {
	 fin >> x;
	 if (x == 'O')
	    value[i][j] = true;
	 else
	    value[i][j] = false;
      }

   cellToNode.resize(rows, cols);
}

void maze::print(int goalI, int goalJ, int currI, int currJ)
// Print out a maze, with the goal and current cells marked on the
// board.
{
   cout << endl;

   if (goalI < 0 || goalI >= numRows() || goalJ < 0 || goalJ > numCols())
      throw rangeError("Bad value in maze::print");

   if (currI < 0 || currI >= numRows() || currJ < 0 || currJ > numCols())
      throw rangeError("Bad value in maze::print");

   for (int i = 0; i <= numRows()-1; i++)
   {
      for (int j = 0; j <= numCols()-1; j++)
      {
	 if (i == goalI && j == goalJ)
	    cout << "*";
	 else
	    if (i == currI && j == currJ)
	       cout << "+";
	    else
	       if (value[i][j])
		  cout << " ";
	       else
		  cout << "X";	  
      }
      cout << endl;
   }
   cout << endl;
}

bool maze::isLegal(int i, int j)
// Return the value stored at the (i,j) entry in the maze, indicating
// whether it is legal to occupy cell (i,j).
{
   if (i < 0 || i >= numRows() || j < 0 || j >= numCols())
      throw rangeError("Bad value in maze::isLegal");

   return value[i][j];
}

bool maze::isAdjacent(int sourceRow, int sourceCol, 
                      int destRow, int destCol)
//Return true if the position given by (row1, col1)
// is adjacent to (row2, col2)
{
   //Return false for illegal coordinates (out-of-range)
   if (destRow < 0 || destCol < 0
       || destRow >= numRows() || destCol >= numCols())
      return false;

   //Return false if source cell is the destination cell
   if ((destRow == sourceRow && destCol == sourceCol))
      return false;

   //Finally, check if the source and destination cells are legal
   if (!isLegal(sourceRow, sourceCol) || !isLegal(destRow, destCol))
      return false;

   //The cells are adjacent. Return true
   else 
      return true;
} // end isAdjacent

void maze::createEdges()
//Creates one edge in mazeGraph for every pair, from
// source node to destination node.
{
   //for each row in the maze
   for (int sourceRow=0; sourceRow<numRows(); sourceRow++)

      //for each column in the maze
      for (int sourceCol=0; sourceCol<numCols(); sourceCol++)
      {
	 //Make a new edge for every adjacent cell
	 //in an up-down or left-right direction
	 int rowOffset[4] = {0, 0, 1, -1};
	 int colOffset[4] = {1, -1, 0, 0};

	 for (int idx=0; idx<4; idx++)
	 {
	    
	    if (isAdjacent(sourceRow, sourceCol,
			   sourceRow + rowOffset[idx], 
			   sourceCol + colOffset[idx]))
	       makeNewEdge(sourceRow, sourceCol, 
			   sourceRow + rowOffset[idx],
			   sourceCol + colOffset[idx]);
	 }
      }
} //end createEdges()

void maze::createNodes()
//Creates nodes in mazeGraph for every cell that is valid
{
   //foreach row
   for (int row = 0; row < numRows(); row++)

      //foreach col
      for (int col = 0; col < numCols(); col++)
      {

	 //make a new node if (row, col) is a legal move
	 if (isLegal(row, col))
	    makeNewNode(row, col);
      }
}

void maze::makeNewEdge(int sourceRow, int sourceCol, 
                       int destRow, int destCol)
//Create new edge between graph nodes given by 
// sourceRow/Col and destRow/Col
//Note that this will be called twice for every pair 
// of nodes, resulting in a bidirectional graph
{
   int sourceNode = getMap(sourceRow, sourceCol);
   int destNode = getMap(destRow, destCol);
   mazeGraph.addEdge(sourceNode, destNode);
}

void maze::makeNewNode(int row, int col)
//Make a new node, and associate the row, col
// to the nodeId 
{
   int nodeId = mazeGraph.addNode(1);
   setMap(row, col, nodeId);
   setReverseMap(row, col);
}

void maze::findPaths()
//Wrapper to findShortestPath1() and 
// findShortestPath2() as dictated in spec.
{
   cout << "Finding shortest path with depth first search..." << endl;
   findShortestPath1();

   //clear shortestPath
   while (!shortestPath.empty())
      shortestPath.pop();

   cout << endl;
   cout << "Finding shortest path with breadth first search..." << endl;
   findShortestPath2();
}

void maze::findShortestPath1()
//Uses dfs recursively.  If no solutions are found, 
// print message.  After finding a solution, print each
// subsequent step from the start point
{
   int startNode = getMap(currentRow, currentCol);
   int goalNode = getMap(goalRow, goalCol);
   stack<nodeAndDir> currentPath;

   dfsRecursive(startNode, currentPath);

   if (shortestPath.size() == 0)
   {
      cout << "No Solution" << endl;
      return;
   }

   //We need to reverse the shortestPath - 
   // this is because dfsRecursive pushes the final move last
   shortestPath = reverseStack(shortestPath);

   printPath(shortestPath);
} // end findShortestPath1

void maze::findShortestPath2()
//Uses bfs.  If no solutions are found, 
// print message.  After finding a solution, print each
// subsequent step from the start point
{
   currentRow = 0;
   currentCol = 0;

   shortestPath = bfs();
   
   if (shortestPath.size() == 0)
   {
      cout << "No Solution" << endl;
      return;
   }

   printPath(shortestPath);
} // end findShortestPath2

stack<nodeAndDir> maze::bfs()
//Find the goal and return a stack of 
//nodes and directions to print out
{
   int startNode = getMap(currentRow, currentCol);
   int goalNode = getMap(goalRow, goalCol);
   queue<int> bfsQueue;

   //Creat a lookup table that returns the previous node
   // from the index
   vector<int> nodeMap(mazeGraph.numNodes());

   nodeMap[startNode] = -1; //Start Has no prev node

   //make all nodes unvisited
   mazeGraph.clearVisit();

   //push v into queue
   bfsQueue.push(startNode);
   mazeGraph.visit(startNode);

   while (!bfsQueue.empty())
   {
      int queueFront = bfsQueue.front();
      
      //get a list of all neighbors
      vector<int> neighbors = getValidNeighbors(queueFront);
      for (int idx=0; idx<neighbors.size(); idx++)
      {
	 int neighborId = neighbors[idx];
	 nodeAndDir currDir;

	 nodeMap[neighborId] = queueFront;

	 //build the nodeAndDir struct to keep track of path's directions
	 currDir.nodeId = queueFront;
	 currDir.direction = getDirection(queueFront, neighborId);

	 mazeGraph.visit(neighborId);
	 //if found goal - build the instructions to the
	 // end goal by tracing the nodeMap
	 if (neighborId == goalNode)
	    return traceMap(nodeMap);

	 bfsQueue.push(neighborId);
      }

      bfsQueue.pop();
   }
} // end bfs

stack<nodeAndDir> maze::traceMap(vector<int> map)
//Convert a vector that maps all nodes to it's previous node
// to a stack of directions that we will print out in 
// findShortestPath2
{
   stack<nodeAndDir> returnStack;

   int goalNode = getMap(goalRow, goalCol);
   int nextNode = goalNode;
   int currentNode= nextNode;
   
   //For every node in the path from start to goal
   while (currentNode != -1)
   {
      //get the current node and the direction to the next node
      nodeAndDir curr;
      int prevNode = map[currentNode];
      curr.nodeId = currentNode;

      //If this is the goal, we don't have a need for direction 
      if (currentNode == goalNode)
	 curr.direction = "Finished!";
      else
	 curr.direction = getDirection(currentNode, nextNode);
      
      //Push the node and direction to the returnStack
      returnStack.push(curr);
      
      //Reset values for next iteration
      nextNode = currentNode;
      currentNode = prevNode;
   }

   return returnStack;
}


void maze::printPath(stack<nodeAndDir> path)
//print each step for solving maze
//nodes are storred in a stack of nodeAndDir structs
{
   //For every element in path stack
   while (!path.empty())
   {
      //get the nodeId and the direction to the next node
      nodeAndDir currentNode = path.top();
      int id = currentNode.nodeId;
      string direction = currentNode.direction;
      currentRow = getReverseMapI(id);
      currentCol = getReverseMapJ(id);
      path.pop();

      //Print the maze...
      print(currentRow, currentCol, goalRow, goalCol);      
      //...and the direction to the next cell
      cout << direction << endl;
   }
}

stack<nodeAndDir> maze::reverseStack(stack<nodeAndDir> stack1)
//Reverse a stack of nodeAndDir 
{
   stack<nodeAndDir> stack2;
   while (!stack1.empty())
   {
      stack2.push(stack1.top());
      stack1.pop();
   }
   return stack2;
}
      
string maze::getDirection(int currentNodeId, int neighborNodeId)
//Return the direction from currentNode to neighborNodeId
// ie - "Go up" "Go right" etc.
// We can assume that currentNodeId != neighborNodeId
{
   stack<int> direction;
   int currentRow = getReverseMapI(currentNodeId);
   int currentCol = getReverseMapJ(currentNodeId);
   int neighborRow = getReverseMapI(neighborNodeId);
   int neighborCol = getReverseMapJ(neighborNodeId);

   int rowOffset = neighborRow - currentRow;
   int colOffset = neighborCol - currentCol;

   switch (rowOffset)
   {
      case 1:
	 return "Go down";
      case -1:
	 return "Go up";
   }

   switch (colOffset)
   {
      case 1:
	 return "Go right";
      case -1:
	 return "Go left";
   }	 

} // end getDirection


void maze::dfsRecursive(int currentNodeId, stack<nodeAndDir> &currentPath)
//As shown in class, except to go through all possible solutions
{
   int goalNodeId = getMap(goalRow, goalCol);
   nodeAndDir currentDir;

   //mark the currentNodeId as visited
   mazeGraph.visit(currentNodeId);


   //check if we found the goal
   if ( currentNodeId == goalNodeId)
   {
      //If the currentPath to the goal is the shortest...
      if (currentPath.size() < shortestPath.size() || 
         shortestPath.size() == 0)
      {
	 //Make the last element on the shortestPath the goalId 
	 shortestPath = currentPath;
	 nodeAndDir prev = shortestPath.top();
	 int prevNode = prev.nodeId;
	 nodeAndDir finalDir;
	 finalDir.nodeId = currentNodeId;
	 finalDir.direction = "Finished!";
	 shortestPath.push(finalDir);
      }
   }
   
   vector<int> neighborVect = getValidNeighbors(currentNodeId);

   //For each neighboring node that is not visited
   for (int idx = 0; idx<neighborVect.size(); idx++)
   {
      int neighborNodeId = neighborVect[idx];
      currentDir.nodeId = currentNodeId;
      currentDir.direction = getDirection(currentNodeId,
                                          neighborNodeId);
      currentPath.push(currentDir);
      dfsRecursive(neighborNodeId, currentPath);
   }

   //Unwinding phase - unvisit the currentNodeId 
   //and pop it off the current Path
   mazeGraph.unVisit(currentNodeId);
   if (!currentPath.empty())
      currentPath.pop();

} // end dfsRecursive()

vector<int> maze::getValidNeighbors(int currentNodeId) 
//Return neighbors of currentNodeId that are not visited
{
   int currentNodeRow = getReverseMapI(currentNodeId);
   int currentNodeCol = getReverseMapJ(currentNodeId);

   vector<int> adjNodes;
   
   //Keep all possible left,right,top,bottom offsets
   int rowOffset[4] = {0, 0, 1, -1};
   int colOffset[4] = {1, -1, 0, 0};

   //Foreach possible direction
   for (int idx=0; idx<4; idx++)
   {
      int adjNodeId = getMap(currentNodeRow + rowOffset[idx],
			     currentNodeCol + colOffset[idx]);
      if ( adjNodeId != -1 && !mazeGraph.isVisited(adjNodeId) )
	 adjNodes.push_back(adjNodeId);
   }

   return adjNodes;

} //end getValidNeighbors


void maze::mapMazeToGraph()
// Create the mazeGraph that represents the legal moves in the maze m.
{
   //Create the graph
   createNodes();
   createEdges();

   //Declare the start as upper left cell
   currentRow = 0;
   currentCol = 0;
   //... and the goal as lower right cell
   goalRow = numRows()-1;
   goalCol = numCols()-1;
}

int main(int argc, char* argv[])
{
   char x;
   ifstream fin;
   
   // Read the maze from the file.
   string fileName = (argc == 2) ? argv[1] : "maze.txt";

   fin.open(fileName.c_str());
   if (!fin)
   {
      cerr << "Cannot open " << fileName << endl;
      return (1);
   }

   try
   {
      while (fin && fin.peek() != 'Z')
      {
	 maze m(fin);
	 m.mapMazeToGraph();
	 m.findPaths();
      }
   }
   catch (indexRangeError &ex) 
   { 
      cout << ex.what() << endl; return (1);
   }
   catch (rangeError &ex)
   {
      cout << ex.what() << endl; return (1);
   }
}
